package 常见算法.分治之快速排序;

import java.util.Random;

/**
 * @Date 2024/6/13 20:23
 * @description: 实现快排
 * .            https://leetcode.cn/problems/sort-an-array/description/
 * @Author LittleNight
 */
public class likou912 {


    // 练习快速排序
    public int[] sortArray4(int[] nums) {
        int n = nums.length;
        qsort4(0, n - 1, nums);
        return nums;
    }

    private void qsort4(int l, int r, int[] nums) {
        if(l >= r) return;

        // 1. 随机找一个基准值划分区间, 进行分三块
        int key = nums[new Random().nextInt(r - l + 1) + l];
        // int left = l - 1, right = r + 1, i = 0;
        // 万分注意, i 是从 l 开始遍历的, 不是从 0 开始, 每次都要变化的
        int left = l - 1, right = r + 1, i = 0;
        // [l, left] [left + 1, right - 1] [right, r]

        // 2. 核心操作:数组分三块
        while(i < right) {
            if(nums[i] < key) swap(++left, i++, nums);
            else if(nums[i] == key) i++;
            else swap(--right, i, nums);
        }
        // [l, left] [left + 1, right - 1] [right, r] 中间是相等的, 不用排序
        // 3. 左右进行递归
        qsort4(l, left, nums);
        qsort4(right, r, nums);
    }

    private void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }


    // 练习快速排序
    public int[] sortArray2(int[] nums) {
        int n = nums.length;
        qsort2(0, n - 1, nums);
        return nums;
    }
    // 先整体进行分块排序, 在左右区间进行排序
    private void qsort2(int l, int r, int[] nums) {
        if(l >= r) return;

        // 1. 划分区间, 进行分三块
        // left 标记小于 key 的最右侧， right 表示大于 key 的最左侧, i 遍历整个数组
        int left = l - 1, right = r + 1, i = l;
        int key = nums[new Random().nextInt(r - l + 1) + l];

        // 2. 数组分三块, 核心代码
        while(i < right) {
            if(nums[i] < key) swap2(++left, i++, nums);
            else if(nums[i] == key) i++;
            // 此处注意 i 没有加加
            else swap2(--right, i, nums);
        }
        // [l, left] [left + 1, right - 1] [right, r] 中间是相等的, 不用排序
        // 3. 递归排序左右区间
        qsort2(l, left, nums);
        qsort2(right, r, nums);
    }

    // 快速排序
    public int[] sortArray3(int[] nums) {
        int n = nums.length;
        // 传入下标
        qsort3(nums, 0, n - 1);
        return nums;
    }

    // 是一个递归的写法
    private void qsort3(int[] nums, int l, int r) {
        // 递归出口， 如果区间没法在划分，直接返回
        if(l >= r) return;

        // 划分区间. 然后分块排序
        int left = l - 1, right = r + 1, i = l;
        int key = nums[new Random().nextInt(r - l + 1) + l];

        while(i < right) {
            if(nums[i] < key) swap2(++left, i++, nums);
            else if(nums[i] == key) i++;
            else swap2(--right, i, nums);
        }

        // 划分完之后， 在划分左侧和右侧的区间
        qsort3(nums, l, left);
        qsort3(nums, right, r);
    }

    private void swap2(int i, int j, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
